/* TwentyFour.java
 * Author: liuex
 * 2007-12-18 ����04:06:47
 *
 * Note: 
 */
package org.lex.tf.core;

import java.util.*;

public class TwentyFour
{
	/**
	 * �ҳ���һ���ܼ����24�ı��ʽ<br>
	 * bugs:<br>
	 * �������� 1, 1, 2, 9 -> (1+2)*(9-1) ������������㲻��
	 */
	public TwentyFour()
	{}

	public Collection<String> find( int a, int b, int c, int d )
	{
		int[] src = new int[]{ a, b, c, d };
		Collection<Expression> e = this.find( 24, src );
		ArrayList<String> finds = new ArrayList<String>( e.size() );
		for( Iterator<Expression> iter = e.iterator(); iter.hasNext(); )
			finds.add( iter.next().toString() );
		return finds;
	}

	private Collection<Expression> find( int expect, int[] src )
	{
		if( 1 == src.length )
		{
			if( expect == src[0] )
			{
				Collection<Expression> finds = new ArrayList<Expression>( 1 );
				finds.add( new Expression( expect ) );
				return finds;
			}
			else
				return Collections.emptyList();
		}
		Collection<Expression> finds = new LinkedList<Expression>();
		Collection<Expression> e = null;
		// 1,3
		for( int i = 0; i < src.length; i++ )
		{
			int v = src[i];
			int[] subSrc = this.newArray( src, i );
			if( v < expect )
			{
				e = this.findG( expect, v, subSrc );
				finds.addAll( e );
			}
			else
			// ( v > expect )
			{
				e = this.findL( expect, v, subSrc );
				finds.addAll( e );
			}
			// else
			// //v == key
			// {
			// e = this.findG( expect, v, subSrc );
			// finds.addAll( e );
			// e = this.findL( expect, v, subSrc );
			// finds.addAll( e );
			// }
		}
		// 2,2
		return finds;
	}

	/**
	 * value < key
	 * 
	 * @param expect
	 * @param value
	 * @param src
	 * @return
	 */
	private Collection<Expression> findG( int expect, int value, int[] src )
	{
		Collection<Expression> finds = new LinkedList<Expression>();
		// add
		int key2 = expect - value;
		Iterator<Expression> iter = this.find( key2, src ).iterator();
		while( iter.hasNext() )
			finds.add( iter.next().add( value ) );
		// mul
		boolean mul = Expression.canDiv( expect, value );
		if( false == mul )
			return finds;
		key2 = expect / value;
		iter = this.find( key2, src ).iterator();
		while( iter.hasNext() )
			finds.add( iter.next().mul( value ) );
		return finds;
	}

	/**
	 * value > key
	 * 
	 * @param expect
	 * @param value
	 * @param src
	 * @return
	 */
	private Collection<Expression> findL( int expect, int value, int[] src )
	{
		Collection<Expression> finds = new LinkedList<Expression>();
		// minus
		int key2 = value - expect;
		Iterator<Expression> iter = this.find( key2, src ).iterator();
		while( iter.hasNext() )
			finds.add( new Expression( value ).minus( iter.next() ) );
		// div
		boolean mul = Expression.canDiv( value, expect );
		if( false == mul )
			return finds;
		key2 = value / expect;
		iter = this.find( key2, src ).iterator();
		while( iter.hasNext() )
			finds.add( new Expression( value ).div( iter.next() ) );
		return finds;
	}

	private int[] newArray( int[] array, int exclusiveIndex )
	{
		int[] a = new int[array.length - 1];
		int i = 0;
		for( int j = 0; j < array.length; j++ )
		{
			if( j == exclusiveIndex )
				continue;
			else
			{
				a[i] = array[j];
				i++;
			}
		}
		return a;
	}
}
